import java.util.ArrayList;
import java.util.List;

/**
 * 842. 将数组拆分成斐波那契序列
 * https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/
 */
public class Solutions_842 {
    public static void main(String[] args) {
        String str = "123456579";  // output: {123, 456, 579}
//        String str = "11235813";  // output:  {1, 1, 2, 3, 5, 8, 13}
//        String str = "112358130";  // output:  {}
//        String str = "0123";  // output: {}
//        String str = "0000";  // output: {0, 0, 0, 0}
//        String str = "1011";  // output: {1, 0, 1, 1}
//        String str = "1101111";  // output:  {110,  1,  111} or {11, 0, 11, 11}

        List<Integer> result = splitIntoFibonacci(str);
        System.out.println(result);
    }

    public static List<Integer> splitIntoFibonacci(String S) {
        List<Integer> res = new ArrayList<>();
        if (S == null || S.length() < 3) {
            // 特殊情况判断（S 长度小于 3，即不足 3 个数字，一定无法组成斐波那契数列）
            return res;
        }
        char[] arr = S.toCharArray();
        backtrack(res, arr, 0);
        return res;
    }

    public static boolean backtrack(List<Integer> res, char[] arr, int start) {
        if (start == arr.length) {
            // 结束条件：arr 中全部元素都遍历到了，如果 res 中元素超过 3 个
            // 说明 arr 中存在一个长度为 3 的斐波那契数列
            return res.size() >= 3;
        }
        long num = 0;
        for (int i = start; i < arr.length; i++) {
            if (i > start && num == 0) {
                // 剪枝：arr[i - 1] 是 '0', 那么 arr[i - 1] * 10 + arr[i] 无法组成数字
                break;
            }
            num = num * 10 + (arr[i] - '0');
            if (num > Integer.MAX_VALUE) {
                // 剪枝：所计算的数字大于 2^31 - 1
                break;
            }
            if (res.size() >= 2) {
                // 数列中存在 2 个以上的数值时，第 3 个数等于前 2 个数值的和，才能组成斐波那契数列
                int m = res.get(res.size() - 1);
                int n = res.get(res.size() - 2);
                if (m + n < num) {
                    // 剪枝：再往后循环，num 只会起来越大
                    break;
                } else if (m + n > num) {
                    // 当前计算值小于数列中前 2 个数的和，那么继续取后面的字符
                    continue;
                }
            }
            // 添加元素到 res 中
            res.add((int) num);
            // 递归
            boolean flag = backtrack(res, arr, i + 1);
            if (flag) {
                // 当前 res 中的元素可以与 arr[i + 1, arr.length - 1] 中的数字，组成一个斐波那契数列
                // 那么提前结束
                return true;
            }
            // 删除
            res.remove(res.size() - 1);
        }
        return false;
    }
}
